Network traffic management requires hardware implementation for scheduling the delivery of network packets, and for traffic shaping. For this, a computer employs a scheduler which is a computer program designed to perform functions, such as network packet scheduling, traffic shaping, and initiation and termination of specified tasks. Hardware schedulers utilize external SRAM and DRAM memory devices to store control blocks of scheduling elements. Because of the expense of external SRAM memory devices, an important consideration is to reduce the number of such devices to better control costs of manufacture. However, it is still necessary to be able to quickly and accurately execute searches for programs with complex flow patterns.
A number of features are found in related art devices, but none of these devices embody the combination of features that are found in the present invention. For example, U.S. Pat. No. 6,330,584 B1 discloses systems and methods for multi-tasking, resource sharing and execution of computer instructions. The task of scheduling is performed by a hardware scheduler requiring no operating system. Simple techniques are provided to synchronize shared resource access between different tasks in a multi-tasking, pipelined processor. Consecutive instructions are executed by different tasks, thereby eliminating the need to purge an instruction execution pipeline of subsequent instructions when a previous instruction cannot be completed. The systems implement external memory and control areas to accommodate the scheduling elements.
U.S. Pat. No. 6,092,180 discloses a method for scheduling instructions in a pipelined environment. Pipeline latencies and resource utilization are measured by sampling hardware while the instructions are executing.
U.S. Pat. No. 5,845,072 discloses a method for parallel and pipelining transference of data between integrated circuits using a common macro interface. The method uses standard hardware design language.
U.S. patent application Publication 2001/0049711 A1 discloses a pipeline processing type of shaping method in which strict shaping processing can be implemented for a connection at varied speed by adding a circuit configuration.
U.S. Pat. No. 5,835,745 discloses a hardware instruction scheduler for short execution unit latencies. The scheduler also includes a pattern of past histories.
Other non-patented sources disclose hardware schedulers and instruction processing; pipelined schedules with hardware-software codesigns and/or synthetic algorithm for pipelined data paths with conditional module sharing/resource sharing; or hardware-software co-synthesis of hierarchical distributed embedded system architectures.
At very high data flow rates, e.g. 10 Gbps design point, hardware scheduler implementation typically stores all functional queue control block content in external SRAM devices to meet media speed performance requirements. There are at least three problems associated with this approach.
First, SRAM devices usually are associated with higher cost compared to DRAM devices, thus increasing system design cost. Second, SRAM devices are more limited in terms of capacity compared to DRAM devices. Third, scheduling functions are becoming complex, thereby requiring: (a) a large number of functional queue control blocks, and (b) large size control blocks to store the required information. For example implementation from Azanda Networks (one of the better scheduler implements currently known in the industry) only uses SRAM devices to cope with the functional requirements.
A goal of scheduler design is to be technology independent. For high data transfer rates, the scheduler architecture shall be an open architecture such that the scheduler can be part of the PowerNP software offering if the network processor has enough processing power to perform the scheduler function in addition to the packet forwarding functions.
The design of the scheduler in ingress configuration provides per flow queuing for switching. In the egress configuration, the scheduler provides per flow queuing, traffic shaping, and scheduling functions. The scheduler design is based on a work conserving concept such that the scheduler shall always work on a frame, i.e., there is no working cycle spent with no frame being dequeued.
A scheduler includes the following components:                Flow Queues: Frames are enqueued in a flow queue by the NPC (network processor complex). A flow queue is attached to one or two Schedule Control Blocks (SCBs).        An SCB is an object that is subject to scheduling by the scheduler. Each SCB has exactly one flow queue associated with it. Once an SCB is selected by the scheduler, a frame from the corresponding flow queue is moved to the appropriate target port queue and the SCB will be reconnected to the scheduler.        Target Port Queues (TPQ) with associated Queue Control Block (QCB): Acts as an elastic queue. All frames in the TPQ will be transmitted onto the port.        Hierarchy Control Blocks (HCBs): Behaves like a TP queue at each hierarchy level. All frames belonging to the queue will be transmitted to the next level of aggregated hierarchy queue till the TPQ has been reached.In addition to the components described above, a scheduler contains the following scheduling units:        Circular Calendar: This is a non-work conserving calendar that provides guaranteed bandwidth service by scheduling according to absolute time and the length of each frame. This is an entity shared by all the flow queues.        Square Calendar: This is a work-conserving calendar that schedules frames based on Weighted Fair Queueing (WFQ) mechanism among the queues attached to the calendar. The square calendar will be selected when the circular calendar has nothing for the clock tick.        Triangular Calendar: This is a non-work conserving calendar and is actually a purgatory that is used to regulate the traffic of a queue attached according to absolute time. When a queue or hierarchy control block has been attached to the purgatory, the queue or hierarchy control block is temporarily disabled and cannot transmit frames until it has been removed from the purgatory and attached to the scheduling calendars.        